package com.example.demo.leetcode;

import java.util.*;

public class _347_前K个高频元素 {

    public static void main(String[] args) {
        int[] nums = {1, 2};
        int k = 2;

        int[] ints = topKFrequent(nums, k);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 方法一：堆
     * <p>
     * 时间复杂度：O(nlog(n)) :其中 n 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(n) 的时间。
     * 随后，我们遍历「出现次数数组」，由于堆的大小至多为 n，因此每次堆操作需要O(log(k)) 的时间，共需 O(nlog(n)) 的时间。二者之和为 O(nlog(n))。
     *
     * <p>
     * 空间复杂度：O(n),哈希表的大小为 O(N)，而堆的大小为 O(N)，共计为 O(N)。
     *
     * @param nums
     * @param k
     * @return {@link int[]}
     * @author WangYX
     * @date 2024/03/12 14:08
     */
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer num = map.getOrDefault(nums[i], 0);
            map.put(nums[i], num + 1);
        }

        Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(entry -> -entry.getValue()));

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
        iterator.forEachRemaining(queue::offer);

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll().getKey();
        }
        return res;
    }
}
